package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/09/23 21:29
 **/
public class Day22_2_Num113_Ⅱ_PathSum {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            dfs(root, targetSum, new ArrayList<>());
            return res;
        }
        private void dfs(TreeNode root, int targetSum, List<Integer> ret){
            if(root == null) return;
            if(root.left == null && root.right == null && targetSum == root.val){
                ret.add(root.val);
                res.add(new ArrayList<>(ret));
                ret.remove(ret.size()-1);
                return;
            }
            ret.add(root.val);
            dfs(root.left, targetSum -= root.val, ret);
            dfs(root.right, targetSum -= root.val, ret);
            ret.remove(ret.size()-1);
        }
    }
}